#include <stdio.h>
#include <stdlib.h>
#define MAX 100
#define ElementType int

typedef struct Array
{
    ElementType arr[MAX];
    int len;//所放的元素个数
}Arr;

//初始化
void InitArray(Arr *a)
{
    for(int i = 0; i < MAX; i++)
    {
        a->arr[i] = 0;
    }
    a->len = 0;
}

//插入
//尾插  
void InsertTail(Arr *a,ElementType element)
{
    //数组满
    if(a->len >= MAX)
    {
        printf("out of range!\n");
        return;
    }

    a->arr[a->len++] = element;
}
//头插
void InsertHead(Arr *a,ElementType element)
{
    //数组满
    if(a->len >= MAX)
    {
        printf("out of range!\n");
        return;
    }

    for(int i = a->len; i > 0; i--)
    {
        a->arr[i] = a->arr[i-1];
    }
    a->arr[0] = element;
    a->len++;
}
//中间插
void InsertByIndex(Arr *a,int index,ElementType element)
{
    //数组满
    if(a->len >= MAX)
    {
        printf("out of range!\n");
        return;
    }
    if(index < 0 || index > a->len)
    {
        printf("invalid place!\n");
        return;
    }
    for(int  i = a->len; i > index; i--)
    {
        a->arr[i] = a->arr[i-1];
    }
    a->arr[index] = element;
    a->len++;
}

//删除
//按位置删
void RemoveByIndex(Arr *a,int index)
{
    if(index < 0 || index >= a->len)
    {
        printf("非法位置!\n");
        return;
    }

    for(int i = index; i < a->len - 1; i++)
    {
        a->arr[i] = a->arr[i+1];
    }
    a->len--;
}

//按值删
void RemoveByElement(Arr *a,ElementType element)
{
    for(int i = 0; i < a->len; i++)
    {
        if(a->arr[i] == element)
        {
            RemoveByIndex(a,i);
            i--;
        }
    }
}

//按位置改
void UpDataByIndex(Arr *a,int index,ElementType element)
{
    if(index < 0 || index >= a->len)
    {
        printf("非法位置!\n");
        return;
    }

    a->arr[index] = element;
}

void UpDataByElement(Arr *a,ElementType oldValue,ElementType newValue)
{
    for(int i = 0; i < a->len; i++)
    {
        if(a->arr[i] == oldValue)
        {
            a->arr[i] = newValue;
        }
    }
}

//查找
//按位置查找
ElementType *FindByIndex(Arr *a,int index)
{
    if(index < 0 || index >= a->len)
    {
        printf("非法位置!\n");
        return NULL;
    }
    return &a->arr[index];
}

//按值查找
int *FindByElement(Arr *a,ElementType element)
{
    int *indexArr = (int*)malloc(sizeof(int) * (a->len + 1));
    if(indexArr == NULL)
        return NULL;

    // int count = 0;
    // for(int i = 0; i < a->len; i++)
    // {
    //     if(a->arr[i] == element)
    //     {
    //         count++;
    //         indexArr[count] = i;
    //     } 
    // }
    // indexArr[0] = count;
    // return indexArr;

    int count = 0;
    for(int i = 0; i < a->len; i++)
    {
        if(a->arr[i] == element)
        {
            indexArr[count] = i;
            count++;
        } 
    }
    indexArr[count] = -1;
    return indexArr;
}

//排序
void FastSort(Arr *a,int start,int end)
{
    if(start >= end)
        return;
    int left = start;
    int right = end;
    ElementType temp = a->arr[left];
    
    while(left < right)
    {
        while(left < right && a->arr[right] > temp)
        {
            right--;
        }
        if(left < right)
        {
            a->arr[left] = a->arr[right];
            left++;
        }
        while(left < right && a->arr[left] < temp)
        {
            left++;
        }
        if(left < right)
        {
            a->arr[right] = a->arr[left];
            right--;
        }
    } 

    a->arr[left] = temp;
    FastSort(a,start,left - 1);
    FastSort(a,right + 1,end);
}

//去重
void Dumplicate(Arr *a)
{
    FastSort(a,0,a->len-1);
    for(int i = 1; i < a->len; i++)
    {
        if(a->arr[i] == a->arr[i-1])
        {
            RemoveByIndex(a,i);
            //防止三个及以上连续的数
            i--;
        }
    }
}

//找交集
Arr* FindInsection(Arr *a1,Arr *a2)
{
    Arr *p = (Arr*)malloc(sizeof(Arr));
    if(p == NULL)
    {
        return NULL;
    }
    InitArray(p);

    for(int i = 0; i < a1->len; i++)
    {
        for(int j = 0; j < a2->len; j++)
        {
            if(a1->arr[i] == a2->arr[j])
            {
                InsertTail(p,a1->arr[i]);
                //找到就跳出内循环,节省时间
                break;
            }
        }
    }    
    Dumplicate(p);
    return p;
}

//找并集
Arr* FindUnionSet(Arr *a1,Arr *a2)
{
    Arr *p = (Arr*)malloc(sizeof(Arr));
    if(p == NULL)
    {
        return NULL;
    }
    InitArray(p);

    for(int i = 0; i < a1->len; i++)
    {
        InsertTail(p,a1->arr[i]);
    }

    for(int i = 0; i < a2->len; i++)
    {
        InsertTail(p,a2->arr[i]);
    }

    Dumplicate(p);

    return p;
}

//合并两个数列(两个已经有序的数列,合并成一个新的有序数列)
//归并排序
Arr *Merge(Arr *a1,Arr *a2)
{
    Arr *p = (Arr*)malloc(sizeof(Arr));
    if(p == NULL)
    {
        return NULL;
    }
    InitArray(p);

    int i = 0;
    int j = 0;
    while(i < a1->len && j < a2->len)
    {
        if(a1->arr[i] > a2->arr[j])
        {
            InsertTail(p,a2->arr[j]);
            j++;
        }
        else
        {
            InsertTail(p,a1->arr[i]);
            i++;
        }
    }

    while(i < a1->len)
    {
        InsertTail(p,a1->arr[i]);
        i++;
    }
    while(j < a2->len)
    {
        InsertTail(p,a2->arr[j]);
        j++;
    }
    return p;
}

//二分查找
int BinarySearch(Arr *a,ElementType element)
{
    int left = 0;
    int right = a->len - 1;
    
    while(left <=  right)
    {
        int mid = left + (right - left)/2;
        if(a->arr[mid] == element)
        {
            return mid;
        }
        if(a->arr[mid] < element)
        {
            left = mid + 1;
        }
        if(a->arr[mid] > element)
        {
            right = mid - 1;
        }
    }
    return -1;
}

//遍历(一个一个访问)
void Travel(Arr *a)
{
    printf("len : %d\n",a->len);
    printf("=============================================\n");
    for(int i = 0; i < a->len; i++)
    {
        printf("%d ",a->arr[i]);
    }
    printf("\n");
    printf("=============================================\n\n");
}

int main()
{
    Arr a;
    InitArray(&a);
    for(int i = 0; i < 10; i++)
    {
        InsertTail(&a,i+1);
    }
    for(int i = 0; i < 10; i++)
    {
        InsertHead(&a,i+1);
    }
    Travel(&a);
    // InsertByIndex(&a,2,24);
    // RemoveByIndex(&a,2);
    // RemoveByElement(&a,8);
    // UpDataByIndex(&a,2,24);
    // UpDataByElement(&a,1,23);
    // Travel(&a);
    // ElementType *ptr = FindByIndex(&a,3);
    // if(ptr == NULL)
    // {
    //     printf("没找到!\n");
    //     return -1;
    // }
    // else
    // {
    //     printf("找到了%d!\n",*ptr);
    // }
    
    // int *ap = FindByElement(&a,9);
    // if(ap != NULL)
    // {
    // //     for(int i = 1; i <= ap[0]; i++)
    // //     {
    // //         printf("%d ",ap[i]);
    // //     }
    // //     printf("\n");

    //     int i = 0;
    //     while(ap[i] != -1)
    //     {
    //         printf("%d ",ap[i]);
    //         i++;
    //     }
    //     printf("\n");
    // }
    // free(ap);
    FastSort(&a,0,a.len - 1);
    Travel(&a);

    Arr a1;
    InitArray(&a1);
    for(int i = 0; i < 10; i++)
    {
        InsertTail(&a1,i+1);
    }
    Travel(&a1);
    Arr a2;
    InitArray(&a2);
    for(int i = 0; i < 10; i++)
    {
        InsertTail(&a2,i+2);
    }
    Travel(&a2);
    Arr *in = Merge(&a1,&a2);
    Travel(in);

    printf("%d\n",BinarySearch(in,6));
 
    return 0;
}